"""
手动实现K均值聚类算法
只使用Python标准库
"""

import random
import math


def euclidean_distance(point1, point2):
    """
    计算两个点之间的欧氏距离
    
    参数:
        point1: 第一个点（列表或元组）
        point2: 第二个点（列表或元组）
    
    返回:
        欧氏距离
    """
    if len(point1) != len(point2):
        raise ValueError("两个点的维度必须相同")
    
    sum_squared_diff = sum((a - b) ** 2 for a, b in zip(point1, point2))
    return math.sqrt(sum_squared_diff)


def assign_cluster(x, c):
    """
    将数据点x分配到最近的聚类中心c
    
    参数:
        x: 数据点（列表或元组）
        c: 聚类中心列表，每个元素是一个聚类中心（列表或元组）
    
    返回:
        最近的聚类中心的索引
    """
    if not c:
        raise ValueError("聚类中心列表不能为空")
    
    min_distance = float('inf')
    closest_center_idx = 0
    
    for idx, center in enumerate(c):
        distance = euclidean_distance(x, center)
        if distance < min_distance:
            min_distance = distance
            closest_center_idx = idx
    
    return closest_center_idx


def Kmeans(data, k, epsilon, iteration):
    """
    K均值聚类算法
    
    """
    if not data:
        raise ValueError("数据不能为空")
    
    if k <= 0:
        raise ValueError("聚类数量k必须大于0")
    
    if k > len(data):
        raise ValueError("聚类数量k不能大于数据点数量")
    
    # 获取数据维度
    dim = len(data[0])
    
    # 1. 初始化聚类中心：随机选择k个数据点作为初始聚类中心
    centers = [list(data[i]) for i in random.sample(range(len(data)), k)]
    
    # 存储上一次的聚类中心，用于判断收敛
    prev_centers = None
    
    # 迭代
    for iter_count in range(iteration):
        # 2. 将每个数据点分配到最近的聚类中心
        labels = [assign_cluster(x, centers) for x in data]
        
        # 3. 更新聚类中心为每个簇的均值
        new_centers = []
        for center_idx in range(k):
            # 找到属于当前簇的所有数据点
            cluster_points = [data[i] for i in range(len(data)) if labels[i] == center_idx]
            
            if not cluster_points:
                # 如果某个簇没有数据点，保持原中心不变
                new_centers.append(centers[center_idx][:])
            else:
                # 计算簇的均值作为新的聚类中心
                new_center = []
                for dim_idx in range(dim):
                    dim_sum = sum(point[dim_idx] for point in cluster_points)
                    new_center.append(dim_sum / len(cluster_points))
                new_centers.append(new_center)
        
        # 4. 检查是否收敛
        if prev_centers is not None:
            max_change = 0
            for i in range(k):
                change = euclidean_distance(prev_centers[i], new_centers[i])
                if change > max_change:
                    max_change = change
            
            if max_change < epsilon:
                # 收敛，停止迭代
                centers = new_centers
                break
        
        prev_centers = [center[:] for center in new_centers]
        centers = new_centers
    
    # 最后一次分配标签
    labels = [assign_cluster(x, centers) for x in data]
    
    return centers, labels


# 测试代码
if __name__ == "__main__":
    # 示例数据：简单的2D数据点
    test_data = [
        [1.0, 1.0],
        [1.5, 2.0],
        [3.0, 4.0],
        [5.0, 7.0],
        [3.5, 5.0],
        [4.5, 5.0],
        [3.5, 4.5],
    ]
    
    print("测试数据:")
    for i, point in enumerate(test_data):
        print(f"  点{i}: {point}")
    
    print("\n运行K均值聚类 (k=2, epsilon=0.01, max_iterations=100)...")
    centers, labels = Kmeans(test_data, k=2, epsilon=0.01, iteration=100)
    
    print("\n聚类结果:")
    print(f"聚类中心:")
    for i, center in enumerate(centers):
        print(f"  中心{i}: {center}")
    
    print(f"\n数据点分配:")
    for i, (point, label) in enumerate(zip(test_data, labels)):
        print(f"  点{i} {point} -> 簇{label}")